package com.example.leetcode.c1_c100.c54;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
 *
 * 示例 1:
 *
 * 输入:
 * [
 *  [ 1, 2, 3 ],
 *  [ 4, 5, 6 ],
 *  [ 7, 8, 9 ]
 * ]
 * 输出: [1,2,3,6,9,8,7,4,5]
 * 示例 2:
 *
 * 输入:
 * [
 *   [1, 2, 3, 4],
 *   [5, 6, 7, 8],
 *   [9,10,11,12]
 * ]
 * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/spiral-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 螺旋矩阵
 * @author zhanpengguo
 * @date 2020-09-14 15:55
 */
public class Solution {



    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new LinkedList<>();
        if (matrix.length == 0) {
            return res;
        }
        // 方向 0-右，1-下，2-左，3-上
        int direct = 0;
        int x = 0;
        int y = 0;
        // 已走过的坐标
        boolean[][] used = new boolean[matrix.length][matrix[0].length];
        // 开始向右
        while (true) {
            if (x == matrix.length || y == matrix[0].length || x < 0 || y < 0) {
                return res;
            }
            if (used[x][y]) {
                return res;
            }
            used[x][y] = true;
            res.add(matrix[x][y]);
            // 向右
            if (direct == 0) {
                if (y == matrix[0].length - 1 || used[x][y + 1]) {
                    // 向右走不通，变成向下
                    direct++;
                    x++;
                    continue;
                } else {
                    y++;
                }
            }
            // 向下
            if (direct == 1) {
                if (x == matrix.length - 1 || used[x + 1][y]) {
                    // 向下走不通，变成向左
                    direct++;
                    y--;
                    continue;
                } else {
                    x++;
                }
            }
            // 向左
            if (direct == 2) {
                if (y == 0 || used[x][y - 1]) {
                    // 向左走不通，变成向上
                    direct++;
                    x--;
                    continue;
                } else {
                    y--;
                }
            }
            // 向上
            if (direct == 3) {
                if (x == 0 || used[x - 1][y]) {
                    // 向上走不通，变成向右
                    direct = 0;
                    y++;
                } else {
                    x--;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] ints = new int[3][4];
        ints[0] = new int[]{1, 2, 3, 4};
        ints[1] = new int[]{5, 6, 7, 8};
        ints[2] = new int[]{9,10,11,12};
        ints = new int[2][1];
        ints[0] = new int[]{3};
        ints[1] = new int[]{2};
        List<Integer> list = solution.spiralOrder(ints);
        System.out.println(list);
    }
}
